
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:

    def __init__(self):
        pass

    def createTree(self, nums: list):
        def level(index):
            if index >= len(nums) or nums[index] is None:
                return None
            root = TreeNode(nums[index])
            root.left = level(2 * index + 1)
            root.right = level(2 * index + 2)
            return root
        return level(0)

    def preorderTree(self, root: TreeNode) -> list:
        res = []
        def preorder(root):
            if root:
                res.append(root.val)
                preorder(root.left)
                preorder(root.right)
        preorder(root)
        return res

    def midTree(self, root: TreeNode) -> list:
        res = []
        def mid(root):
            if root:
                mid(root.left)
                res.append(root.val)
                mid(root.right)
        mid(root)
        return res

    def postTree(self, root: TreeNode) -> list:
        res = []
        def post(root):
            if root:
                post(root.left)
                post(root.right)
                res.append(root.val)
        post(root)
        return res

    def checkMirror(self, root: TreeNode) -> bool:
        def isMirror(left, right):
            if left is None and right is None:
                return True
            if left is None or right is None or left.val != right.val:
                return False
            return isMirror(left.left, right.right) and isMirror(left.right, right.left)
        return isMirror(root.left, root.right)

    def checkChild(self, A: TreeNode, B: TreeNode) -> bool:
        def sub(A, B):
            if B is None:
                return True
            if A is None:
                return False
            return A.val == B.val and sub(A.left, B.left) and sub(A.right, B.right)

        if A is None or B is None:
            return False
        if A.val != B.val:
            return self.checkChild(A.left, B) or self.checkChild(A.right, B)

        return sub(A, B) or self.checkChild(A.left, B) or self.checkChild(A.right, B)
            
    def isCheckChild(self, A: TreeNode, B: TreeNode) -> bool:
        def check(A, B):
            if B is None:
                return True
            if A is None:
                return False
            return A.val == B.val and check(A.left, B.left) and check(A.right, B.right)
        if A is None or B is None:
            return False
        if A.val != B.val:
            return self.isCheckChild(A.left, B) or self.isCheckChild(A.right, B)
        return check(A, B) or self.isCheckChild(A.left, B) or self.isCheckChild(A.right, B)

    def invertTree(self, root: TreeNode) -> TreeNode:
        if root is None:
            return None
        root.left, root.right = root.right, root.left
        self.mirrorTree(root.left)
        self.mirrorTree(root.right)
        return root

    # 层序遍历反向
    def levelOrder2(self, root: TreeNode) -> list:
        if root is None:
            return []
        res = []
        q = []
        q.append(root)
        while q:
            size = len(q)
            t = []
            for _ in range(size):
                node = q.pop(0)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
                t.append(node.val)
            res.append(t)
        return res[::-1]

    # 层序遍历
    def levelOrder(self, root: TreeNode) -> list:
        if root is None:
            return []
        res = []
        q = []
        q.append(root)
        while q:
            t = []
            size = len(q)
            for _ in range(size):
                node = q.pop(0)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
                t.append(node.val)
            res.append(t)
        return res

    # 右视图
    def rightView(self, root: TreeNode) -> list:
        res = []
        q = []
        q.append(root)
        while q:
            res.append(q[0].val)
            size = len(q)
            print(size)
            for _ in range(size):
                node = q.pop(0)
                if node.right:
                    q.append(node.right)
                if node.left:
                    q.append(node.left)
        return res

    def maxDeepTree(self, root: TreeNode) -> list:
        if root is None:
            return 0
        left = self.maxDeepTree(root.left)
        right = self.maxDeepTree(root.right)
        return 1 + max(left, right)

    def minDeepTree(self, root: TreeNode) -> list:
        if root is None:
            return 0
        if root.left is None:
            return 1 + self.minDeepTree(root.right)
        if root.right is None:
            return 1 + self.minDeepTree(root.left)
        return 1 + min(self.minDeepTree(root.left), self.minDeepTree(root.right))

    def getAllRoad(self, root: TreeNode) -> list:
        def dfs(tree):
            if tree is None:
                return
            road.append(str(tree.val))
            if tree.left is None and tree.right is None:
                # print(road)
                res.append('->'.join(road))
            dfs(tree.left)
            dfs(tree.right)
            print(road)
            road.pop()
        res = []
        road = []
        dfs(root)
        return res

    def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
        def dfs(root, targetSum):
            if root is None:
                return False
            if root.val == targetSum and root.left is None and root.right is None:
                return True
            return dfs(root.left, targetSum - root.val) or dfs(root.right, targetSum - root.val)
        return dfs(root, targetSum)

    def roadSum(self, root: TreeNode, targetSum: int) -> bool:
        def dfs(root):
            if root is None:
                return
            t.append(root.val)
            if root.left is None and root.right is None:
                s = sum(t)
                res.append(s)
            dfs(root.left)
            dfs(root.right)
            t.pop()
        if root is None:
            return None
        res = []
        t = []
        dfs(root)
        if targetSum in res:
            return True
        else:
            return False

    def hasPathSumList(self, root: TreeNode, targetSum: int) -> list:
        def dfs(root, targetSum):
            if root is None:
                return False
            road.append(root.val)
            if root.val == targetSum and root.left is None and root.right is None:
                res.append(road.copy())
            dfs(root.left, targetSum - root.val)
            dfs(root.right, targetSum - root.val)
            road.pop()
        if root is None:
            return []
        res = []
        road = []
        dfs(root, targetSum)
        return res

    def buildTree(self, preorder: list, inorder: list) -> TreeNode:
        def build(preorder, inorder, p1, p2, i1, i2):
            root_val = preorder[p1]
            pos = indexes[root_val]
            pass
        n = len(inorder)
        indexes = {}
        for i in range(n):
            indexes[inorder[i]] = i
        # build(preorder, inorder, 0, n-1, 0, n-1)
        pass





    #      1
    #     / \ 
    #    2   3
    #   / \  / \
    #  8  4  6  7

if __name__ == '__main__':
    s = Solution()
    # nums = [1,2,3,8,4,6,7]
    # nums = [1,2,2,3,4,4,3]
    # tree1 = s.createTree(nums)

    # res = s.preorderTree(tree1)
    # print(res)

    # res = s.midTree(tree1)
    # print(res)

    # res = s.postTree(tree1)
    # print(res)

    # nums = [1,3,3,3,4,4,3]
    # tree1 = s.createTree(nums)
    # res = s.checkMirror(tree1)
    # print(res)

    # A = s.createTree([3,4,5,1,2])
    # B = s.createTree([4,1,2])
    # res = s.isCheckChild(A, B)
    # print(res)

    # A = s.createTree([1,2,3,8,4,6,7])
    # res = s.mirrorTree(A)
    # print(s.preorderTree(res))

    # A = s.createTree([3, 9, 20, None, None, 15, 7])
    # res = s.levelOrder2(A)
    # print(res)

    # A = s.createTree([1, 2, 3, None, 5, None, 4])
    # A = s.createTree([1, 2, None, 5, None, None, None, 4])
    # res = s.rightView2(A)
    # print(res)

    # A = s.createTree([3, 9, 20, None, None, 15, 7, None, None, None, None, 1,2])
    # res = s.maxDeepTree(A)
    # print(res)

    # A = s.createTree([3,9,20,8,None,15,7])
    # res = s.minDeepTree(A)
    # print(res)

    # A = s.createTree([1, 2, 3, 3, 5])
    # res = s.getAllRoad(A)
    # print(res)
    # res = s.hasPathSum(A, 7)

    # A = s.createTree([5, 4, 8, 11, None, 13, 4, 7, 2, None, None, None, None, 5, 1])
    # res = s.hasPathSumList(A, 22)
    # print(res)

    # p = s.createTree([5, 4, 8, 11, None, 13, 4, 7, 2, None, None, None, None, 5, 1])
    res = s.buildTree([3, 9, 20, 15, 7], [9, 3, 15, 20, 7])
    print(res)
